package shuanfa;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr={53,23,4,8,157,15};
        radixSort(arr);
    }
    public static void radixSort(int[] arr){
        //得到这个数组的最大数
        int max=0;
        for (int i=0;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //定义一个二维数组，来表示10个桶，每个桶就是一个一维数组
        int[][] bucket=new int[10][arr.length];
        //定义一个一维数组来记录每个桶每次放入的数据个数
        int[] bucketElmentCounts=new int[10];
        for (int j=0,n=1;j<maxLength;j++,n*=10){
            //针对每个元素的对应位进行排序，第一次是个位，第二次是十位，第三次是百位
            for (int k=0;k<arr.length;k++){
                //取出每个元素对应位的值
                int digitOfElment=arr[k]/n%10;
                //放入对应的桶中
                bucket[digitOfElment][bucketElmentCounts[digitOfElment]]=arr[k];
                bucketElmentCounts[digitOfElment]++;
            }
            //按照放入桶中的顺序，依次取出数字放入原数组
            int index=0;
            for (int m=0;m<bucketElmentCounts.length;m++){
                //桶中有数据才取出数据
                if (bucketElmentCounts[m]!=0){
                    for (int s=0;s<bucketElmentCounts[m];s++){
                        //取出桶中元素放入数组
                        arr[index]=bucket[m][s];
                        index++;
                    }
                }
                //取完后将桶中数据个数重置为零
                bucketElmentCounts[m]=0;
            }
            System.out.println("第"+(j+1)+"轮排序后："+ Arrays.toString(arr));
        }
    }
}
